<?php
interface IHashMapKey {
	public function hashCode();
	public function equals($other);
}

class HashMapKeyWrapper implements IHashMapKey {
	private $_content;

	public function __construct(& $content) {
		$this->_content = $content;
	}

	public function hashCode() {
		return strval($this->_content);
	}

	public function getWrapped() {
		return $this->_content;
	}

	public function equals($other) {
		if ($other instanceof HashMapKeyWrapper) {
			return $this->_content == $other->_content;
		}
		return false;
	}
}

class HashMapEntry {
	private $_key;
	private $_value;

	public function __construct($key, &$value) {
		$this->_key = $key;
		$this->_value = $value;
	}
	
	public function getKey()
	{
		return $this->_key;
	}
	
	public function getValue()
	{
		return $this->_value;
	}
}

final class HashMap {
	/** Two dimensions array (&lt;hashcode&gt;=>array(&lt;objects&gt;) used to store keys. */
	private $_keys;
	/** Two dimensions array (&lt;hashcode&gt;=>array(&lt;objects&gt;) used to store values. */
	private $_values;
	/** Last index used. */
	private $_lastIndex;
	/** Array storing all "real" keys (no wrapped key). */
	private $_realkeys;
	/** Array used to store all values. */
	private $_flatValues;

	/**
	 * Create a new HashMap.
	 * @return HashMap
	 */
	public function __construct() {
		$this->clear();
	}

	/**
	 * Add or update an entry into the current hash map.
	 * 
	 * @param mixed $key Key to associate.
	 * @param mixed &$value Value to store.
	 * 
	 * @return mixed Old value associated to the key, null on first assignment.
	 */
	public function put($key, & $value) {
		$oldValue = null;
		$offset = $this->WrapObjectIfNeeded($key);
		list ($hashcode, $hash, $idx) = $this->findIndexesFor($offset);
		if ($hash === null) {
			$this->_keys[$hashcode] = array ();
			$this->_values[$hashcode] = array ();
			$this->_lastIndex[$hashcode] = 0;
			$hash = $hashcode;
		}
		if ($idx === null) {
			$idx = $this->_lastIndex[$hash];
			$this->_lastIndex[$hash] = $idx +1;
		} else {
			$oldValue = $this->_values[$hash][$idx];
		}
		$this->_realkeys[$hash.":".$idx] = $key;
		$this->_flatValues[$hash.":".$idx] = $value;
		
		$this->_keys[$hash][$idx] = $offset;
		$this->_values[$hash][$idx] = $value;

		return $oldValue;
	}

	/**
	 * Add all key/value pair from another hashmap or an array into the current hashmap.
	 * 
	 * @param mixed Hashmap or Array to put into the current hashmap.
	 * 
	 * @return bool Indicates if the object can be put or not.
	 */
	public function putAll($collection) {
		if ($collection instanceof HashMap) {
			foreach ($collection->_keys as $hash => $keys) {
				foreach ($keys as $idx => $key) {
					$this->put($key, $collection->_values[$hash][$idx]);
				}
			}
			return true;
		}
		if (is_array($collection)) {
			foreach ($collection as $key => $value) {
				$this->put($key, $value);
			}
			return true;
		}
		return false;
	}

	/**
	 * Removes a given key from the map.
	 *
	 * @param string $key Key to removes.
	 * 
	 * @return bool Indicates if the given key can be found and removed or not.
	 */
	public function remove($key) {
		list ($hashcode, $hash, $idx) = $this->findIndexesFor($key);
		if ($hash != null && $idx != null)
		{
			unset($this->_key[$hash][$idx]);
			unset($this->_values[$hash][$idx]);
			unset($this->_realkeys[$hash.":".$idx]);
			unset($this->_flatValues[$hash.":".$idx]);

			return true;
		}
		return false;
	}

	/**
	 * Get the value associated to the offset.
	 * 
	 * @param mixed $offset Key to find
	 * 
	 * @return mixed Value associated to the key, null if not found.
	 */
	public function get($offset) {
		list ($hashcode, $hash, $idx) = $this->findIndexesFor($offset);
		if ($hash !== null && $idx !== null) {
			return $this->_values[$hash][$idx];
		}

		return null;
	}

	/**
	 * Clears all the entry in the map
	 */
	public function clear() {
		$this->_keys = array ();
		
		$this->_values = array ();
		$this->_lastIndex = array ();
		
		$this->_realkeys = array();
		$this->_flatValues = array ();
	}

	/**
	 * Gets array of all contained keys.
	 *
	 * @return array All contained keys.
	 */
	public function keys() {
		return array_values($this->_realkeys);
	}

	/**
	 * Gets array of all contained values.
	 *
	 * @return array All contained values.
	 */
	public function values() {
		return array_values($this->_flatValues);
	}

	/**
	 * Returns the number of elements in the map.
	 *
	 * @return int Number of elements in the map.
	 */
	function size() {
		return sizeof($this->_realkeys);
	}

	/**
	 * Checks if the map is empty.
	 *
	 * @return bool Indicates if the map is empty or not.
	 */
	function isEmpty() {
		return ($this->size() == 0);
	}

	/**
	 * Checks if a given key exists
	 *
	 * @param mixed $key Key to find.
	 * @return bool Indicates if the key exists or not.
	 */
	public function containsKey($key) {
		list ($hashcode, $hash, $idx) = $this->findIndexesFor($key);
		return ($hash != null && $idx != null);
	}

	/**
	 * Checks if a given value exists.
	 *
	 * @param mixed $value Value to find.
	 * @param bool $strict Whether data type must be checked.
	 * 
	 * @return bool Indicates if value has been found or not.
	 */
	public function containsValue($value, $strict = false) {
		return (array_search($value, $this->_flatValues, $strict) !== false);
	}
	
	/**
	 * Returns a set view of the mappings contained in this map. 
	 * 
	 * @return array An array of HashMapEntry for all elements contained in this map.
	 */
	public function entrySet()
	{
		$entry = array();
		foreach ($this->_realkeys as $hash => $key)
		{
			$entry[$hash] = new HashMapEntry($key, $this->_flatValues[$hash]);
		}
		
		return $entry;
	}
	
	/**
	 * Find index of offset in keys array. It will return an array containing 3 fields : 
	 * <ul>
	 * <li>first, the computed hashcode;</li>
	 * <li>next, the hashcode if $this->_keys[<hashcode>];</li>
	 * <li>last, the index of the key in $this->_keys[&lt;hashcode&gt;] array</li>
	 * </ul>
	 * If the second or the third element is set to null... so the offset doesn't exists in keys array.
	 * 
	 * @param mixed $offset Offset to find in keys array. 
	 * 
	 * @return array an array like (&lt;hashcode&gt;, [&lt;hashcode&gt;|null], [&lt;offset_index&gt;|null])
	 */
	protected function findIndexesFor($offset) {
		$offset = $this->WrapObjectIfNeeded($offset);
		$hashcode = $offset->hashCode();
		if (array_key_exists($hashcode, $this->_keys)) {
			$idx = null;
			foreach ($this->_keys[$hashcode] as $i => $value) {

				if ($value->equals($offset)) {
					$idx = $i;
				}
			}
			return array (
				$hashcode,
				$hashcode,
				$idx
			);
		}

		return array (
			$hashcode,
			null,
			null
		);
	}

	/**
	 * Wrap the given offset into an HashMapKeyWrapper object that can be used as key for
	 * the hashmap.
	 * 
	 * @param mixed $offset Offset to find in keys array. 
	 * 
	 * @return HashMapKeyWrapper Wrapped object into an hashmap key.
	 */
	private function WrapObjectIfNeeded($object) {
		if (!($object instanceof IHashMapKey)) {
			return new HashMapKeyWrapper($object);
		}

		return $object;
	}
}

class Hashmap2 {

	/**
	 * Sorts the map
	 *
	 * @link http://www.php.net/sort
	 * @param int $flags Sort flags
	 */
	function sort($flags = SORT_REGULAR) {
		sort($this->elements, $flags);
	}

	/**
	 * Sorts the map in reverse order (highest to lowest)
	 *
	 * @param int $flags Sort flags
	 */
	function reverseSort($flags = SORT_REGULAR) {
		rsort($this->elements, $flags);
	}

	/**
	 * Sorts the map by values based on an user-defined comparison function
	 *
	 * @param string|array $callback User defined function
	 */
	function customSort($callback) {
		usort($this->elements, $callback);
	}

	/**
	 * Get map size
	 *
	 * @return int
	 */
	function size() {
		return sizeof($this->elements);
	}

	/**
	 * Checks if the map is empty
	 *
	 * @return bool
	 */
	function isEmpty() {
		return ($this->size() == 0);
	}

	/**
	 * Builds an array representation of the hash map
	 *
	 * @return array
	 */
	function toArray() {
		return $this->elements;
	}

	/**
	 * Builds a string representation of the hash map
	 *
	 * @return string
	 */
	function __toString() {
		return sprintf("Hashmap object{\n%s\n}", dumpArray($this->elements));
	}
}

class A {
	public $toto;
	public function __construct($toto = "toto") {
		$this->toto = $toto;
	}

	public function __toString() {
		return $this->toto;
	}
}

$m = new HashMap();
$v = new A();
$m->put("A", $v);
var_dump($m->get("A"));
$v->toto = "tutu";
var_dump($m->get("A"));

$v = array (
	1,
	2
);
$m->put("B", $v);
var_dump($m->get("B"));
$v[] = "tutu";
var_dump($m->get("B"));

echo uniqid("HashMapKey");

?>
